package com.zyk.leetcode;

/**
 * @author zhangsan
 * @date 2021/4/15 14:12
 */
public class C1139 {

    // https://leetcode-cn.com/problems/largest-1-bordered-square/
    // 给你一个由若干 0 和 1 组成的二维网格 grid，请你找出边界全部由 1 组成的最大 正方形 子网格，并返回该子网格中的元素数量。如果不存在，则返回 0。
    // 1. 暴力尝试
    public static int largest1BorderedSquare(int[][] grid) {
        int maxLen = 0;
        int height = grid.length;
        int width = grid[0].length;
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                if (grid[i][j] == 1) {
                    int curLen = maxLen;
                    while (i + curLen < height && j + curLen < width) {
                        boolean flag1 = true;
                        for (int temp_i = i, temp_j = j; temp_i < i + curLen + 1 && temp_j < j + curLen + 1; temp_i++, temp_j++) {
                            if (grid[i][temp_j] == 0 || grid[temp_i][j] == 0) {
                                flag1 = false;
                                break;
                            }
                        }
                        if (flag1 == false) break;
                        boolean flag2 = true;
                        for (int temp_i = i + curLen, temp_j = j + curLen, _i = temp_i, _j = temp_j; temp_i > i && temp_j > j; temp_i--, temp_j--) {
                            if (grid[temp_i][_j] == 0 || grid[_i][temp_j] == 0) {
                                curLen++;
                                flag2 = false;
                                break;
                            }
                        }
                        if (flag2 == false) continue;
                        maxLen = ++curLen;
                    }
                }
            }
        }
        return maxLen * maxLen;
    }


    // for test
    public static void main(String[] args) {
        int[][] grid = {
                {1, 1, 1},
                {1, 0, 1},
                {1, 1, 1}
        };
        System.out.println(largest1BorderedSquare(grid));
    }

}
